Top K Numbers介紹大綱:

《上篇》
-介紹Binary Heap(二元堆積)的結構與特性
-Binary Heap與陣列的關係

《中篇》
-Binary Heap種類
-Heap Sort: 了解什麼是heapify，以及heapify如何利用binary heap實現陣列排序

《下篇》
-Top K Numbers Pattern介紹與應用題型

在今天開始進入Top K Numbers之前，先來認識一下Binary Heap吧!

由於Heap在資料結構這一塊，有一部分可以再更深入探討與學習，不過為了忠於今天的主題Top K Numbers(其實是因為已經馬拉松進度落後，所以只能點到為止)，僅會簡單介紹Heap Sort，那我們就趕快開始吧!

什麼是Binary Heap(二元堆積)?
Binary Heap是一種資料結構，它的概念就是一個Binary Tree(二元樹)，它所具備的特性如下列幾點:

1. 每個node最多有兩個child，也可能只有一個child或是都沒有
2. 同一階層都是由左至右排列，且不能跳過

source: wikipedia

3.通常使用陣列來實現，可以透過陣列的索引值(indices)直接計算出node與child的位置，因此不需要額外的指針來儲存這些數值之間的關係，如此一來可以節省儲存空間並提高效率。

這一段文字可以用下面的圖示來理解，從下圖中可以看到每個數值在陣列中的排序 跟 在Binary Heap中的排序 之間的對應關係:

source: wikipedia

觀察圖中的相同數字在heap與陣列中的對應位置，不難發現

• left child node的number就是 2 * n
• right chile node的number就是 2 * n + 1

以數字19這個節點來看，數字19的number為2(此時n=2)，left node是17、right node是12，這兩個數字對應的number分別為4(2n)跟5(2n+1)

我們可以利用上述特性，在index跟number之間做轉換，從而得知node在陣列中對應的index。

以上是Heap的大略介紹，下一篇我們要開始學習蹲馬步，了解什麼是Heap Sort。
Reference:
https://medium.com/@Kadai/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B%E5%A4%A7%E4%BE%BF%E7%95%B6-binary-heap-ec47ca7aebac

https://medium.com/starbugs/%E4%BE%86%E5%BE%81%E6%9C%8D%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B%E8%88%87%E6%BC%94%E7%AE%97%E6%B3%95%E5%90%A7-%E6%90%9E%E6%87%82-binary-heap-%E7%9A%84%E6%8E%92%E5%BA%8F%E5%8E%9F%E7%90%86-96768ea30d3f

https://emre.me/coding-patterns/top-k-numbers/#how-to-identify